import java.util.Arrays;

class Solution1 {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Integer[] index1 = new Integer[n];
        Integer[] index2 = new Integer[n];
        for (int i = 0; i < n; i++) index1[i] = index2[i] = i;
        Arrays.sort(index1, (a, b) -> nums1[a] - nums1[b]);
        Arrays.sort(index2, (a, b) -> nums2[a] - nums2[b]);
        System.out.println(Arrays.toString(index1));
        System.out.println(Arrays.toString(index2));
        int cur = 0;
        int begin = 0, end = n - 1;
        int[] ret = new int[n];
        while (cur < n) {
            if(nums1[index1[cur]] > nums2[index2[begin]]) {
                ret[index2[begin++]] = nums1[index1[cur]];
            }else {
                ret[index2[end--]] = nums1[index1[cur]];
            }
            cur++;
        }
        return ret;
    }
}

class Solution2 {
    public int longestPalindrome(String s) {
        int[] hash = new int[128];
        int n = s.length();
        for(int i = 0; i<n; i++) {
            char ch = s.charAt(i);
            hash[ch]++;
        }
        int sum = 0;
        int flag = 0;
        for(int i = 0; i<128; i++) {
            if(hash[i]%2==0) {
                sum += hash[i];
            }else {
                sum += hash[i]-1;
                flag = 1;
            }
        }
        sum += flag;
        return sum;
    }
}

class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int left = 0, right = n;
        int[] ret = new int[n+1];
        int index = 0;
        for(int i = 0; i<n; i++) {
            if(s.charAt(i) == 'I') {
                ret[index++] = left++;
            }else {
                ret[index++] = right--;
            }
        }
        ret[index] = left;
        return ret;
    }
}

public class Test {

}
